package code1.stack_and_queue;

import java.util.Stack;

/**
 * 原题链接：https://leetcode.cn/problems/valid-parentheses/
 */
public class P20 {

    //括号匹配
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        char[] str = s.toCharArray();
        for(int i=0;i<str.length;i++){
            if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
                //左括号，入栈
                stack.push(str[i]);
            }else{
                //右括号，弹出栈顶元素，判断是否为匹配的左括号
                if(stack.isEmpty()){
                    return false;       //若栈空则直接返回false
                }
                char top = stack.pop();
                if(str[i]==')' && top!='('){
                    return false;
                }
                if(str[i]==']' && top!='['){
                    return false;
                }
                if(str[i]=='}' && top!='{'){
                    return false;
                }
            }
        }
        return stack.isEmpty();     //最后栈为空则匹配成功
    }
}
